package com.data_structure_algorithm.data_structure.tree.huff;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @Authror PABLO
 * @Date 2022/4/2 17:44
 * @Desc 赫夫曼编码解压
 */
public class HuffUpZip {

    /**
     * @Description:
     * @Author: PABLO
     * @Date: 2022/4/2 18:03
     * @Params: [huffmanCodes 赫夫曼编码,
     * huffmanBytes 赫夫曼压缩得到的压缩数组]
     * @Return: byte[] 解码后的数组
     **/
    public byte[] decode(Map<Byte, String> huffmanCodes, byte[] huffmanBytes) {
        StringBuilder stringBuilder = new StringBuilder();
        //得到HuffmanBytes对应的二进制字符串 1111000101010110......
        for (int i = 0; i < huffmanBytes.length; i++) {
            //如最后一个字节
            boolean flag = (i == huffmanBytes.length - 1);

            stringBuilder.append(byteToString(!flag, huffmanBytes[i]));
        }

        //System.out.println("---" + stringBuilder.toString());

        //将得到的字符串转为对应字符，这里是map反向查询，通过huffmanCodes的value查询key
        Map<String, Byte> decodeMap = new HashMap<>();
        //将字符串按照赫夫曼编码进行翻转
        for (Map.Entry<Byte, String> byteStringEntry : huffmanCodes.entrySet()) {
            decodeMap.put(byteStringEntry.getValue(), byteStringEntry.getKey());
        }

        //创建集合处存放解码后的数据
        //遍历StringBuilder，匹配map，将对应byte放入list
        List<Byte> list = new ArrayList<>();


        for (int i = 0; i < stringBuilder.length(); ) {
            int localIndex = 1;
            boolean flag = true;
            Byte ele = null;

            while (flag) {

                //localIndex不断后移，通过索引推进得到的二进制字符串直至匹配到decodeMap中对应的value（byte字符）

                int index = i + localIndex;
                if (index > stringBuilder.length()) {
                    break;
                }
                String key = stringBuilder.substring(i, index);
                ele = decodeMap.get(key);//得到的是byte字符
                if (ele == null) {
                    //未匹配到继续后移动
                    localIndex++;
                } else {
                    //匹配到了
                    flag = false;
                }
            }

            //走到这里说明匹配到了一个字符byte
            list.add(ele);


            //步长为上个完整字符长度的下一个，
            // 如取出的第一个字符对应的二进制字符串为11010五位，
            // 下一个从第六位开始匹配下个字符
            i += localIndex;

        }
        //System.out.println(list);

        //将list转为byte数组
        byte[] resultByte = new byte[list.size()];

        for (int i = 0; i < list.size() -1; i++) {

            resultByte[i] = list.get(i);
        }

        return resultByte;
    }

    /**
     * @Description:将压缩后的字节数组转为赫夫曼编码对应的2进制字符串
     * @Author: PABLO
     * @Date: 2022/4/2 17:49
     * @Params: [b 字节
     * flag 是否需要补高位,最后一个字节不补高位    true 需要]
     * @Return: java.lang.String 入参b对应的二进制补码字符串
     **/
    public String byteToString(boolean flag, byte b) {

        //byte 没有转为字符串的函数，Integer有
        int temp = b;
        if (flag) {
            temp |= 256;
        }
        //这里得到的是temp对应的二进制补码
        String toBinaryString = Integer.toBinaryString(temp);
        //TODO 待改进  处理最后1位是负数  处理
        if (flag) { //需要补高位
            String substring = toBinaryString.substring(toBinaryString.length() - 8);
            //System.out.println(substring);
            return substring;
        } else {
            return toBinaryString;
        }

    }
}
